class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
        if x == 1:
            return 1

        low, high = 1, x // 2
        while low <= high:
            mid = low + (high - low) // 2
            if mid > x / mid:
                high = mid - 1
            else:
                low = mid + 1

        return low - 1
        
s = Solution()
print('ss', s.mySqrt(4))
print('ss', s.mySqrt(8))